package org.usmile.algorithms.learn.graph.bfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BiPartitionDetection {
    public boolean isBiPartition(Graph graph) {
        Queue<Integer> queue = new LinkedList<>();
        int[] colors = new int[graph.getV()];
        Arrays.fill(colors, -1);
        boolean[] visited = new boolean[graph.getV()];
        for (int v = 0; v < graph.getV(); v++) {
            if (colors[v] == -1) {
                queue.offer(v);
                colors[v] = 0;
                while (!queue.isEmpty()) {
                    int curr = queue.poll();
                    for (int w : graph.adj(curr)) {
                        if (colors[w] == -1) {
                            queue.add(w);
                            colors[w] = 1 - colors[curr];
                        } else {
                            if (colors[w] == colors[curr]) {
                                return false;
                            }
                        }
                    }
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(8);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);

        System.out.println(new BiPartitionDetection().isBiPartition(graph));
    }
}
